package com.xuanyuan.analysis;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author ：罗发新
 * time  ：2020/6/22 0022  9:13
 * email ：424533553@qq.com
 * desc  : 各种排序的class
 */
class SortClass {


    /* 归并排序  START
    * *********************************************************************************/

    /**
     * 两路归并算法，两个排好序的子序列合并为一个子序列
     *
     * @param arr   需要合并的数组
     * @param left  左边起始索引
     * @param mid   中间索引
     * @param right 右边起始索引
     */
    public void merge(int[] arr, int left, int mid, int right) {
        //辅助数组
        int[] tmp = new int[right + 1 - left];
        //p1、p2是检测指针，k是存放指针
        int p1 = left, p2 = mid + 1, k = 0;

        while (p1 <= mid && p2 <= right) {
            if (arr[p1] <= arr[p2]) {
                tmp[k++] = arr[p1++];
            } else {
                tmp[k++] = arr[p2++];
            }
        }

        //如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
        while (p1 <= mid) {
            tmp[k++] = arr[p1++];
        }

        //如果第二个序列未检测完，直接将后面所有元素加到合并的序列中
        while (p2 <= right) {
            tmp[k++] = arr[p2++];
        }

        //复制回原素组
        if (right + 1 - left >= 0) {
            System.arraycopy(tmp, 0, arr, left, right + 1 - left);
        }
    }

    /**
     * 进行归并排序
     *
     * @param arr        需要排序的数组
     * @param startIndex 数组的开始索引
     * @param endIndex   数组最后一个元素的索引
     */
    public void mergeSort(int[] arr, int startIndex, int endIndex) {
        //当子序列中只有一个元素时结束递归
        if (startIndex < endIndex) {
            //划分子序列
            int mid = (startIndex + endIndex) / 2;
            //对左侧子序列进行递归排序
            mergeSort(arr, startIndex, mid);
            //对右侧子序列进行递归排序
            mergeSort(arr, mid + 1, endIndex);
            //合并
            merge(arr, startIndex, mid, endIndex);
        }
    }

    /* 归并排序  END *********************************************************************************/




    /* 快速排序  START
    * *********************************************************************************/

    /**
     * 1. 当low=height时,此时排序结束，数组已经有序了
     * 2. 获取基准数pivot索引，一般第一个基准索引为0
     * 3. 计算出基准值得所以后，此时左边的数组都小于pivot，右边的数据都大于pivot
     * 4. 采用归并递归的思想，循环执行第3步，直到low-=height，此时排序完成
     *
     * @param arr  源数组
     * @param low  最低排序索引
     * @param high 最高排序索引
     */
    private void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 找寻基准数据的正确索引
            int index = getPivotIndex(arr, low, high);
            // 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
            quickSort(arr, low, index - 1);
            quickSort(arr, index + 1, high);
        }
    }

    /**
     * 获取 排序索引
     * 1.获取数组arr的第一个数为基准数pivot
     * 2.当low<height时,先从右到左扫描,如果arr[height]>=pivot，height--;
     * 如果arr[height]<pivot,它应该放在pivot左边，此时执行arr[low] = arr[high],结束从右到左的扫描
     * 3.当low < high时,从右到左结束扫描后，开始从左到右的扫描。如果arr[low] <= pivot,low++继续扫描;
     * 如果arr[low] > pivot,说明arr[low]应该放在pivot的右边，此时执行arr[high] = arr[low],从右到左扫描结束
     * 4.while循环第一轮结束,如果low < high则继续执行2、3操作查找pivot的索引,此时查找的范围low~height已经缩小了
     * 5.直到low =height，此时low或者height就是pivot的索引
     *
     * @param arr     源数组
     * @param low2    最低排序索引
     * @param height2 最高排序索引
     * @return 基准值的索引位置
     */
    private int getPivotIndex(int[] arr, int low2, int height2) {
        // 基准数据
        int low = low2;
        int height = height2;
        int pivot = arr[low];
        while (low < height) {
            // 当队尾的元素大于等于基准数据时,向前挪动high指针
            while (low < height && arr[height] >= pivot) {
                height--;
            }
            // 如果队尾元素小于tmp了,需要将其赋值给low
            arr[low] = arr[height];
//            low++;
            // 当队首元素小于等于tmp时,向前挪动low指针
            while (low < height && arr[low] <= pivot) {
                low++;
            }
            // 当队首元素大于tmp时,需要将其赋值给high
            arr[height] = arr[low];
//          height--;
        }
        // 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置
        // 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low]
        arr[low] = pivot;
        return low;
    }

    /* 快速排序  END *********************************************************************************/


    /* 堆排序  Start *********************************************************************************/


    /***
     * 构建大根堆
     * @param array  数据源
     */
    private void buildHeap(int[] array) {
        //从右向左，从下到上依次遍历父节点，建立大根堆，时间复杂度：O(n*log2n)
        for (int i = (array.length - 1 - 1) / 2; i >= 0; i--) {
            adjust(array, i, array.length - 1);
        }
    }

    /**
     * 将指定堆构建成大堆根函数
     * 逻辑
     * 1. 如果起始索引无子节点，则跳出该方法
     * 2. 如果只有一个左子节点，进行大小比较并置换值
     * 3. 如果有两个子节点，选择最大值与父节点比较,然后置换其位置。
     * 如果子节点大于父节点，置换完成后，递归进行同样操作，其子节点索引即是函数的start值
     *
     * @param array 源数组
     * @param start 起始索引
     * @param end   结尾索引
     */
    public void adjust(int[] array, int start, int end) {
        // 左子节点的位置
        int leftIndex = 2 * start + 1;
        if (leftIndex == end) {
            //只有一个左节点，进行比较并置换值
            if (array[leftIndex] > array[start]) {
                int temp = array[leftIndex];
                array[leftIndex] = array[start];
                array[start] = temp;
            }
        } else if (leftIndex < end) {
            //有两个子节点
            int temp = array[leftIndex];
            int tempIndex = leftIndex;
            if (array[leftIndex + 1] > array[leftIndex]) {
                temp = array[leftIndex + 1];
                tempIndex = leftIndex + 1;
            }
            if (temp > array[start]) {
                array[tempIndex] = array[start];
                array[start] = temp;
            }
            adjust(array, tempIndex, end);
        }
    }

    /**
     * 在 array 是大堆根的前提下添加元素然后重构大堆根
     *
     * @param array 大堆根数组
     * @param value 添加的元素值
     */
    private int[] addHeap(int[] array, int value) {
        int[] arr = new int[array.length + 1];
        System.arraycopy(array, 0, arr, 0, array.length);
        arr[arr.length - 1] = value;
        int currentIndex = arr.length - 1;
        int parentIndex = (arr.length - 1) / 2;
        while (parentIndex >= 0) {
            if (value > arr[parentIndex]) {
                int temp = arr[parentIndex];
                arr[parentIndex] = value;
                arr[currentIndex] = temp;

                //如果最后一个元素的父节点还有父节点需要继续进行对比
                currentIndex = parentIndex;
                parentIndex = (currentIndex - 1) / 2;
            } else {
                break;
            }
        }

        return arr;
    }

    /**
     * 在 array 是大堆根的前提下删除元素然后重构大堆根
     *
     * @param array       大堆根数组
     * @param deleteIndex 删除元素的索引
     */
    private int[] deleteHeap(int[] array, int deleteIndex) {
        array[deleteIndex] = array[array.length - 1];
        int[] arr = new int[array.length - 1];
        System.arraycopy(array, 0, arr, 0, array.length - 1);
        int lefeIndex = 2 * deleteIndex + 1;
        while (lefeIndex >= arr.length - 1) {
            int maxIndex = lefeIndex;
            if (arr.length - 1 > lefeIndex) {
                if (arr[lefeIndex + 1] > arr[lefeIndex]) {
                    maxIndex = lefeIndex + 1;
                }
            }

            if (arr[maxIndex] > arr[deleteIndex]) {
                int temp = arr[maxIndex];
                arr[maxIndex] = arr[deleteIndex];
                arr[deleteIndex] = temp;
                lefeIndex = 2 * maxIndex + 1;
            } else {
                break;
            }
        }
        return arr;
    }

    /**
     * 堆排序
     *
     * @param array 源数组
     */
    public void heapSort(int[] array) {
        buildHeap(array);
        int tmp;
        //要与root节点置换位置元素的索引
        int end = array.length - 1;
        //n个节点只用构建排序n-1次，最后只有1个元素不用在排序
        for (int i = array.length - 1; i > 0; i--) {
            tmp = array[0];
            array[0] = array[end];
            array[end] = tmp;

            end--;
            //头尾置换后，将堆重新构建为大堆根，置换尾部大元素不参加构建
            //因为除了root节点，其它都是由大到小有序的，所以再次构建大根堆时，不用在进行adjust()前的那个循环
            adjust(array, 0, end);
        }
    }

    /* 堆排序  END *********************************************************************************/



    /* 计数排序  END *********************************************************************************/

    /**
     * 计数算法，适合int类型数据排序，该方法有优化，支持有负数
     * 一种线性排序算法，不需要进行比较，时间复杂度为O(n)。
     *
     * @param array 待排序数组
     * @param max   最大值
     * @param min   最小值
     * @return 返回排序后的数组
     */
    public int[] countSort(int[] array, int max, int min) {
        //1.为了资源，数据不再从0开始，直接从最小到最大,创建临时空间数组
        int[] coutArray = new int[max - min + 1];
        //2.对原始数组元素进行统计,对空间数组index=value - min进行自增,统计了同样的数据
        for (int value : array) {
            coutArray[value - min]++;
        }

        //3.按顺序,空间数组每个元素的值是多少则打印多少次
        int index = 0;
        for (int i = 0; i < coutArray.length; i++) {
            for (int j = 0; j < coutArray[i]; j++) {
                array[index++] = i + min;
            }
        }
        return array;
    }

    /* 计数排序  END *********************************************************************************/


    /* 桶排序  START
    * *********************************************************************************/

    /**
     * 这是一个桶排序，建桶规则是将数据分到arr.length+1 个桶中，然后进行排序整理
     * 该代码中如有9个数据，将数据期数据分到10个桶中。此分配规则不一样，会影响排序效果
     *
     * @param arr 源数组
     */
    public static void bucketSort(int[] arr) {
        // 计算最大值与最小值
        int max = 0;
        int min = 0;
        for (int value : arr) {
            if (max < value) {
                max = value;
            }
            if (min > value) {
                min = value;
            }
        }

        // 计算桶的数量，并创建一个桶集合
        int bucketNum = (max - min) / arr.length + 1;
        List<ArrayList<Integer>> bucketArr = new ArrayList<>();
        for (int i = 0; i < bucketNum; i++) {
            bucketArr.add(new ArrayList<Integer>());
        }

        // 将每个元素放入桶
        for (int i = 0; i < arr.length; i++) {
            int num = (arr[i] - min) / (arr.length);
            bucketArr.get(num).add(arr[i]);
        }

        // 对每个桶进行排序
        for (int i = 0; i < bucketArr.size(); i++) {
            Collections.sort(bucketArr.get(i));
        }

        // 将桶中的元素赋值到原序列
        int index = 0;
        for (int i = 0; i < bucketArr.size(); i++) {
            for (int j = 0; j < bucketArr.get(i).size(); j++) {
                arr[index++] = bucketArr.get(i).get(j);
            }
        }
    }
    /* 桶排序  END *********************************************************************************/


    /* 基数排序  END *********************************************************************************/

    /**
     * 基数排序,该排序被优化，可以支持负数排序
     *
     * @param array 源数组
     */
    public void radixSort(int[] array) {
        //1. 获取最大、最小值
        int max = 0;
        int min = 0;

        for (int value : array) {
            if (max < value) {
                max = value;
            }
            if (min > value) {
                min = value;
            }
        }
        //兼容负数排序
        int absMax = max - min;

        //2. 获取最大值的位数长；
        int times = 0;
        while (absMax > 0) {
            absMax /= 10;
            times++;
        }

        //3. 由于数字的特殊性，数字尾数必定是0~9，可创建10个桶，用于分装数据
        List<List<Integer>> queue = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            List<Integer> q = new ArrayList<>();
            queue.add(q);
        }

        //开始比较,重点
        for (int i = 0; i < times; i++) {
            reconstruction(queue, array, i, min);
        }
    }

    /**
     * 数组位置重构
     * 根据i=0,1,2,将个位，十位，百位的数据重新分组为
     * 【1,11  2,22,42，132】、【1,2  11  22 132 42】、【1,2,11,22,42,132】
     *
     * @param queue 桶集合
     * @param array 源数组
     * @param i     数字位数，如 12345,i=1,2,3,4,5
     */
    private void reconstruction(List<List<Integer>> queue, int[] array, int i, int min) {
        for (int j = 0; j < array.length; j++) {
            // 当j=0,1,2 时分别取的是数字个位，十位，百位上的数据
            // array[j] - min是为了兼容负数
            int x = (array[j] - min) % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
            // 将指定位上为X(x=0~9),放入第x个桶中
            List<Integer> q = queue.get(x);
            q.add(array[j] - min);
        }
        // 当位数i时,从0桶到9桶，一个个取出数据放入源数组中，此时数组顺序第一次改变了
        int count = 0;
        for (int j = 0; j < 10; j++) {
            while (queue.get(j).size() > 0) {
                List<Integer> q = queue.get(j);
                array[count++] = q.get(0) + min;
                q.remove(0);
            }
        }
    }
    /* 基数排序  END *********************************************************************************/

    /**
     * 二叉堆，
     *
     */
    public static void main(String[] args) {

        SortClass sortClass = new SortClass();
        int[] arr = sortClass.generateRandomArray(30);
        System.out.println("准备排序的数组：");
        for (int e : arr) {
            System.out.print(e + " ");
        }

        System.out.println();
        System.out.println();

        // 设计完成
//        System.currentTimeMillis()
        sortClass.radixSort(arr);
        System.out.println("准备排序的数组：" + Arrays.toString(arr));
    }

    /**
     * 生成一个无序的数组
     */
    public int[] generateRandomArray(int n) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = (int) (Math.random() * 100 - 30);
        }
        return arr;
    }


}

